Міністерство Освіти, Науки, Молоді та Спорту України Національний університет «Львівська політехніка» Кафедра ЕОМ
КУРСОВА РОБОТА з дисципліни: «Паралельні та розподілені обчислення» на тему: «Паралельне виконання операцій множення матриць»  Завдання Розробити схему та описати процедуру перемноження матриці А (розмірністю N1*N2) на матрицю В (розмірністю N2*N3) на структурі з восьми процесорів. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму. N1 = 40 N2 = 192 N3 = 159 Таблиця 1. Часові параметри Співвідношення часових параметрів Пояснення  tu=9tz час виконання однієї операції множення  tS=9/10tZ час виконання однієї операції сумування  tP =9/10tZ час виконання однієї операції пересилання даних між процесорами  tz час виконання операції завантаження одних даних  tW=tZ час виконання операції вивантаження одних даних   Таблиця 2. Кодування букв К Р Ф Д Г Е Й С  47 93 233 13 74 171 146 82  2F 5D E9 D 4A AB 92 52   Таблиця 3. Матриця суміжності 1 2 3 4 5 6 7 8  1 0 0 1 0 1 1 1 1  2 0 0 0 1 1 1 0 1  3 1 1 0 0 1 0 0 1  4 0 0 0 0 1 1 0 1  5 0 1 0 0 0 0 1 0  6 1 0 1 0 1 0 1 1  7 1 0 0 1 0 0 0 0  8 0 1 0 1 0 0 1 0   Type = (
i)mod3 + 1 Z= 0909488. Type =(0+9+0+9+4+8+8)mod3+1 = 3 Розподілена пам'ять. Анотація В даній курсовій роботі розроблено алгоритм паралельного перемноження матриць на структурі з восьми процесорів. Завантаження даних відбувається з спільної пам’яті. Вхідні матриці мають розмірності А(40*192) та В(192*159). Робота складається з розрахунку часових характеристик алгоритму, розробки функціональної схеми алгоритму та програмної реалізації. Відповідно до часових затрат паралельного алгоритму визначено його ефективність відносно послідовного. Програмно, алгоритм реалізований на C++ з консольним інтерфейсом, та з використанням MPI. Зміст Вступ. 6 1. Теоретичний розділ. 7 2. Розробка блок - схеми виконання алгоритму. 9 3. Розробка функціональної схеми. 12 4. Розрахунковий розділ 13 5. Розробка програми. 16 СПИСОК ЛІТЕРАТУРИ. 19 Висновок 20 Додаток. 21 Лістинг програми. 21 Вступ. Паралельні обчислювальні системи - комп'ютерні системи, що реалізовують тим або іншим способом паралельну обробку даних на багатьох обчислювальних вузлах для підвищення загальної швидкості розрахунку. Ідея розпаралелення обчислень базується на тому, що більшість завдань можуть бути розділені на набір менших завдань, які можуть бути вирішені одночасно. Зазвичай паралельні обчислення вимагають координації дій. Паралельні алгоритми досить важливі з огляду на постійне вдосконалення багатопроцесорних систем і збільшення числа ядер у сучасних процесорах. Зазвичай простіше сконструювати комп'ютер з одним швидким процесором, ніж з багатьма повільними з тією ж продуктивністю. Однак збільшення продуктивності за рахунок вдосконалення одного процесора має фізичні обмеження, такі як досягнення максимальної щільності елементів та тепловиділення. Зазначені обмеження можна подолати лише шляхом переходу до багатопроцесорної архітектури, що виявляється ефективним навіть у малих обчислювальних системах. Складність послідовних алгоритмів виявляється в обсязі використаної пам'яті та часу (число тактів процесора), необхідних для виконання алгоритму. Розподілені обчислення - спосіб розв'язання трудомістких обчислювальних завдань з використанням двох і більше комп'ютерів, об'єднаних в мережу. Розподілені обчислення є окремим випадком паралельних обчислень, тобто одночасного розв'язання різних частин одного обчислювального завдання декількома процесорами одного або кількох комп'ютерів. Тому необхідно, щоб завдання, що розв'язується було сегментоване — розділене на підзадачі, що можуть обчислюватися паралельно. При цьому для розподілених обчислень доводиться також враховувати можливу відмін...